/**
 * @constructor
 * @param {number} val
 * @param {ListNode|null} [next]
 */
function ListNode(val, next) {
    /** @type {number} */
    this.val = (val === undefined ? 0 : val)
    /** @type {ListNode|null} */
    this.next = (next === undefined ? null : next)
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function (head) {
    //使用一个快指针和一个慢指针
    //快指针每次走2步，慢指针每次走1步
    //长度为奇数时，快指针指向末尾，慢指针在中间
    //长度为偶数时，快指针指向null，慢指针在两个中间节点的后一个
    let fast = head
    let slow = head
    while (fast && fast.next) { //快指针指向末尾或者末尾的下一个null
        fast = fast.next.next
        slow = slow.next
    }
    return slow
};